package com.mango.leet.code.week2.game73;

/**
 * 2190. 数组中紧跟 key 之后出现最频繁的数字
 */

import java.util.*;

/**
 * 给你一个下标从 0 开始的整数数组 nums ，同时给你一个整数 key ，它在 nums 出现过。
 *
 * 统计 在 nums 数组中紧跟着 key 后面出现的不同整数 target 的出现次数。换言之，target 的出现次数为满足以下条件的 i 的数目：
 *
 * 0 <= i <= n - 2
 * nums[i] == key 且
 * nums[i + 1] == target 。
 * 请你返回出现 最多 次数的 target 。测试数据保证出现次数最多的 target 是唯一的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,100,200,1,100], key = 1
 * 输出：100
 * 解释：对于 target = 100 ，在下标 1 和 4 处出现过 2 次，且都紧跟着 key 。
 * 没有其他整数在 key 后面紧跟着出现，所以我们返回 100 。
 * 示例 2：
 *
 * 输入：nums = [2,2,2,2,3], key = 2
 * 输出：2
 * 解释：对于 target = 2 ，在下标 1 ，2 和 3 处出现过 3 次，且都紧跟着 key 。
 * 对于 target = 3 ，在下标 4 出出现过 1 次，且紧跟着 key 。
 * target = 2 是紧跟着 key 之后出现次数最多的数字，所以我们返回 2 。
 *
 *
 * 提示：
 *
 * 2 <= nums.length <= 1000
 * 1 <= nums[i] <= 1000
 * 测试数据保证答案是唯一的。
 */
public class LC2190 {
    public static void main(String[] args) {
        //int[] nums = {2,1,2,1,2,3};
        //int[] nums = {2,2,2,2,3};
        //int[] nums = {1,100,200,1,100};
        //int[] nums = {1,1000,2};
        int[] nums = {1,1};
        int key = 1;
        System.out.println(new Solution().mostFrequent2(nums,key));
    }

    static class Solution {
        /**
         * 思路：
         * 统计key后跟的target出现最多
         */
        public int mostFrequent2(int[] nums, int key) {
            Map<Integer,Integer> map = new HashMap<>();
            int max = 0,result = 0;
            for(int i=0;i<nums.length;i++){
                // 找到key后紧跟着的target
                if(i+1 < nums.length && nums[i] == key){
                    int target = nums[i+1];
                    // 出现1次加1
                    int count = map.getOrDefault(target,0)+1;
                    map.put(target,count);
                    if(max < count){
                        max = count;
                        result = target;
                    }
                }
            }
            return result;
        }
        /**
         * 思路：(不采用）
         * 1. 指针定位到key
         * 2. 记录后跟着的target出现的次数
         * 3. 加入到次数高优先队列
         */
        public int mostFrequent(int[] nums, int key) {
            Map<Integer,Integer> map = new HashMap<>();
            int count = 0;
            int target = 0;
            int max = 0,result = 0;
            for(int i=0;i<nums.length;i++){
                // 找到key后紧跟着的target
                if(i+1 < nums.length && nums[i] == key){
                    target = nums[i+1];
                }
                // 开始计算target出现的次数
                int j=i+1;
                while( j<nums.length && target == nums[j]){
                    count++;
                    j++;
                }
                // 记录次数到map里，如果数值一样则累加次数
                if(count>0) {
                    int sum = map.getOrDefault(target,0)+count;
                    map.put(target,sum);
                    // 下标i跳过出现的次数
                    i = i + count - 1;
                    count = 0;
                    if(max < sum){
                        max = sum;
                        result = target;
                    }
                }
            }
            System.out.println(map.toString());
            return result;
        }
    }
}
